/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-04-24
 * Time: 9:33
 */
//132.分割回文串II
class Solution4 {
    public int minCut(String s) {
        int n = s.length();
        //预处理
        boolean[][] f = new boolean[n][n];
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n;j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    f[i][j] = i+1 < j ? f[i+1][j-1] : true;
                }
            }
        }
        //1.创建dp表
        //dp[i]表示区间[0,i]之间最长子串是否为回文子串
        int[] dp = new int[n];
        //2.初始化
        for(int i = 0; i < n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for(int i = 0; i < n; i++) {
            if(f[0][i]) {
                dp[i] = 0;
            }else {
                for(int j = 1; j < n; j++) {
                    if(f[j][i]) {
                        dp[i] = Math.min(dp[i],dp[j-1]+1);
                    }
                }
            }
        }
        return dp[n-1];
    }
}
